/*
 * Copyright (C) 2007 The Android Open Source Project
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package com.android.dx.ssa;

import java.util.ArrayList;
import java.util.BitSet;
import java.util.HashSet;

/**
 * This class computes dominator and post-dominator information using the
 * Lengauer-Tarjan method. See A Fast Algorithm for Finding Dominators in a
 * Flowgraph T. Lengauer & R. Tarjan, ACM TOPLAS July 1979, pgs 121-141. This
 * implementation runs in time O(n log n). The time bound could be changed to
 * O(n * ack(n)) with a small change to the link and eval, and an addition of a
 * child field to the DFS info. In reality, the constant overheads are high
 * enough that the current method is faster in all but the strangest
 * artificially constructed examples. The basic idea behind this algorithm is to
 * perform a DFS walk, keeping track of various info about parents. We then use
 * this info to calculate the dominators, using union-find structures to link
 * together the DFS info, then finally evaluate the union-find results to get
 * the dominators. This implementation is m log n because it does not perform
 * union by rank to keep the union-find tree balanced.
 */
public final class Dominators {

	/* postdom is true if we want post dominators */
	private final boolean postdom;

	/* {@code non-null;} method being processed */
	private final SsaMethod meth;

	/* Method's basic blocks. */
	private final ArrayList<SsaBasicBlock> blocks;

	/** indexed by basic block index */
	private final DFSInfo[] info;

	private final ArrayList<SsaBasicBlock> vertex;

	/** {@code non-null;} the raw dominator info */
	private final DomFront.DomInfo domInfos[];

	/**
	 * Constructs an instance.
	 * 
	 * @param meth
	 *            {@code non-null;} method to process
	 * @param domInfos
	 *            {@code non-null;} the raw dominator info
	 * @param postdom
	 *            true for postdom information, false for normal dom info
	 */
	private Dominators(SsaMethod meth, DomFront.DomInfo[] domInfos,
			boolean postdom) {
		this.meth = meth;
		this.domInfos = domInfos;
		this.postdom = postdom;
		this.blocks = meth.getBlocks();
		this.info = new DFSInfo[blocks.size() + 2];
		this.vertex = new ArrayList<SsaBasicBlock>();
	}

	/**
	 * Constructs a fully-initialized instance. (This method exists so as to
	 * avoid calling a large amount of code in the constructor.)
	 * 
	 * @param meth
	 *            {@code non-null;} method to process
	 * @param domInfos
	 *            {@code non-null;} the raw dominator info
	 * @param postdom
	 *            true for postdom information, false for normal dom info
	 */
	public static Dominators make(SsaMethod meth, DomFront.DomInfo[] domInfos,
			boolean postdom) {
		Dominators result = new Dominators(meth, domInfos, postdom);

		result.run();
		return result;
	}

	private BitSet getSuccs(SsaBasicBlock block) {
		if (postdom) {
			return block.getPredecessors();
		} else {
			return block.getSuccessors();
		}
	}

	private BitSet getPreds(SsaBasicBlock block) {
		if (postdom) {
			return block.getSuccessors();
		} else {
			return block.getPredecessors();
		}
	}

	/**
	 * Performs path compress on the DFS info.
	 * 
	 * @param in
	 *            Basic block whose DFS info we are path compressing.
	 */
	private void compress(SsaBasicBlock in) {
		DFSInfo bbInfo = info[in.getIndex()];
		DFSInfo ancestorbbInfo = info[bbInfo.ancestor.getIndex()];

		if (ancestorbbInfo.ancestor != null) {
			ArrayList<SsaBasicBlock> worklist = new ArrayList<SsaBasicBlock>();
			HashSet<SsaBasicBlock> visited = new HashSet<SsaBasicBlock>();
			worklist.add(in);

			while (!worklist.isEmpty()) {
				int wsize = worklist.size();
				SsaBasicBlock v = worklist.get(wsize - 1);
				DFSInfo vbbInfo = info[v.getIndex()];
				SsaBasicBlock vAncestor = vbbInfo.ancestor;
				DFSInfo vabbInfo = info[vAncestor.getIndex()];

				// Make sure we process our ancestor before ourselves.
				if (visited.add(vAncestor) && vabbInfo.ancestor != null) {
					worklist.add(vAncestor);
					continue;
				}
				worklist.remove(wsize - 1);

				// Update based on ancestor info.
				if (vabbInfo.ancestor == null) {
					continue;
				}
				SsaBasicBlock vAncestorRep = vabbInfo.rep;
				SsaBasicBlock vRep = vbbInfo.rep;
				if (info[vAncestorRep.getIndex()].semidom < info[vRep
						.getIndex()].semidom) {
					vbbInfo.rep = vAncestorRep;
				}
				vbbInfo.ancestor = vabbInfo.ancestor;
			}
		}
	}

	private SsaBasicBlock eval(SsaBasicBlock v) {
		DFSInfo bbInfo = info[v.getIndex()];

		if (bbInfo.ancestor == null) {
			return v;
		}

		compress(v);
		return bbInfo.rep;
	}

	/**
	 * Performs dominator/post-dominator calculation for the control flow graph.
	 * 
	 * @param meth
	 *            {@code non-null;} method to analyze
	 */
	private void run() {
		SsaBasicBlock root = postdom ? meth.getExitBlock() : meth
				.getEntryBlock();

		if (root != null) {
			vertex.add(root);
			domInfos[root.getIndex()].idom = root.getIndex();
		}

		/*
		 * First we perform a DFS numbering of the blocks, by numbering the dfs
		 * tree roots.
		 */

		DfsWalker walker = new DfsWalker();
		meth.forEachBlockDepthFirst(postdom, walker);

		// the largest semidom number assigned
		int dfsMax = vertex.size() - 1;

		// Now calculate semidominators.
		for (int i = dfsMax; i >= 2; --i) {
			SsaBasicBlock w = vertex.get(i);
			DFSInfo wInfo = info[w.getIndex()];

			BitSet preds = getPreds(w);
			for (int j = preds.nextSetBit(0); j >= 0; j = preds
					.nextSetBit(j + 1)) {
				SsaBasicBlock predBlock = blocks.get(j);
				DFSInfo predInfo = info[predBlock.getIndex()];

				/*
				 * PredInfo may not exist in case the predecessor is not
				 * reachable.
				 */
				if (predInfo != null) {
					int predSemidom = info[eval(predBlock).getIndex()].semidom;
					if (predSemidom < wInfo.semidom) {
						wInfo.semidom = predSemidom;
					}
				}
			}
			info[vertex.get(wInfo.semidom).getIndex()].bucket.add(w);

			/*
			 * Normally we would call link here, but in our O(m log n)
			 * implementation this is equivalent to the following single line.
			 */
			wInfo.ancestor = wInfo.parent;

			// Implicity define idom for each vertex.
			ArrayList<SsaBasicBlock> wParentBucket;
			wParentBucket = info[wInfo.parent.getIndex()].bucket;

			while (!wParentBucket.isEmpty()) {
				int lastItem = wParentBucket.size() - 1;
				SsaBasicBlock last = wParentBucket.remove(lastItem);
				SsaBasicBlock U = eval(last);
				if (info[U.getIndex()].semidom < info[last.getIndex()].semidom) {
					domInfos[last.getIndex()].idom = U.getIndex();
				} else {
					domInfos[last.getIndex()].idom = wInfo.parent.getIndex();
				}
			}
		}

		// Now explicitly define the immediate dominator of each vertex
		for (int i = 2; i <= dfsMax; ++i) {
			SsaBasicBlock w = vertex.get(i);
			if (domInfos[w.getIndex()].idom != vertex.get(
					info[w.getIndex()].semidom).getIndex()) {
				domInfos[w.getIndex()].idom = domInfos[domInfos[w.getIndex()].idom].idom;
			}
		}
	}

	/**
	 * Callback for depth-first walk through control flow graph (either from the
	 * entry block or the exit block). Records the traversal order in the
	 * {@code info}list.
	 */
	private class DfsWalker implements SsaBasicBlock.Visitor {

		private int dfsNum = 0;

		public void visitBlock(SsaBasicBlock v, SsaBasicBlock parent) {
			DFSInfo bbInfo = new DFSInfo();
			bbInfo.semidom = ++dfsNum;
			bbInfo.rep = v;
			bbInfo.parent = parent;
			vertex.add(v);
			info[v.getIndex()] = bbInfo;
		}
	}

	private static final class DFSInfo {

		public int semidom;
		public SsaBasicBlock parent;

		/**
		 * rep(resentative) is known as "label" in the paper. It is the node
		 * that our block's DFS info has been unioned to.
		 */
		public SsaBasicBlock rep;

		public SsaBasicBlock ancestor;
		public ArrayList<SsaBasicBlock> bucket;

		public DFSInfo() {
			bucket = new ArrayList<SsaBasicBlock>();
		}
	}
}
